Sparse signal recovery problems arise in many different applications. In communication systems, the recovery of sparse communication signals from receive signals is of increasing interest.
An n-dimensional communication signal or vector is called sparse if it comprises only a few non-zero entries among the total number of entries n. Sparse communication signals can be recovered from a fewer number of measurements comparing with the total dimension n. Sparseness can appear in different bases, so communication signals can, for example, be represented as sparse communication signals in time domain or in frequency domain.
The recovery of sparse communication signals is usually more computationally extensive than a matrix inverse or pseudo-inverse involved in least squares computations. Moreover, the matrix is usually not invertible, as the system is under-determined.
Common methods for sparse communication signal recovery suffer from high computational complexity and/or low performance. These methods are usually not suitable for use in real time systems.
In E. J. Candes, and T. Tao, “Decoding by linear programming,” IEEE Trans. on Information Theory, vol. 51, no. 12, pp. 4203-4215, December 2005, a linear programming approach is proposed and analyzed.
In T. Cai, L. Wang, “Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise,” IEEE Trans. on Information Theory, v. 57, N. 7, pp. 4680-4688, the problem of sparse signal recovery from incomplete measurements is considered applying an orthogonal matching pursuit method.